package com.problem;

import java.util.HashMap;

/**
 * https://leetcode-cn.com/problems/lru-cache/
 */
public class LRUCache {

    //运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
    //
    //实现 LRUCache 类：
    //LRUCache(int capacity) 以 正整数 作为容量capacity 初始化 LRU 缓存
    //int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    //void put(int key, int value)如果关键字key 已经存在，则变更其数据值value ；如果不存在，则向缓存中插入该组key-value 。
    // 如果插入操作导致关键字数量超过capacity ，则应该 逐出 最久未使用的关键字。
    //
    //函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

//    private final int capacity;
//    private LinkedHashMap<Integer, Integer> cache;
//    private TreeMap<Long, Integer> timeKeyMap;
//    private HashMap<Integer, Long> keyTimeMap;
//
//    public LRUCache(int capacity) {
//        this.capacity = capacity;
//        this.cache = new LinkedHashMap<>(capacity);
//        this.timeKeyMap = new TreeMap<>();
//        this.keyTimeMap = new HashMap<>();
//    }
//
//    public int get(int key) {
//        Integer value = cache.get(key);
//        if (value == null) {
//            return -1;
//        }
//
//        long t = System.nanoTime();
//        Long oldT = keyTimeMap.get(key);
//        timeKeyMap.remove(oldT);
//
//        timeKeyMap.put(t, key);
//        keyTimeMap.put(key, t);
//        return value;
//    }
//
//    public void put(int key, int value) {
//        Integer oldV = cache.get(key);
//        Long expireTime = null;
//        if (oldV == null) {
//            if (cache.size() >= capacity) {
//                Map.Entry<Long, Integer> firstEntry = timeKeyMap.firstEntry();
//                Integer expireKey = firstEntry.getValue();
//                cache.remove(expireKey);
//                keyTimeMap.remove(expireKey);
//                expireTime = firstEntry.getKey();
//                timeKeyMap.remove(expireTime);
//            }
//        }else {
//            timeKeyMap.remove(keyTimeMap.get(key));
//        }
//        long t = System.nanoTime();
//        cache.put(key, value);
//        timeKeyMap.put(t, key);
//        keyTimeMap.put(key, t);
//    }

    // --------------------- ---------------
    private final int capacity;
    private HashMap<Integer, LinkedNode> cache;
    LinkedNode head, tail;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        LinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        //移动到队尾
        remove2Tail(node);

        return node.val;
    }

    public void put(int key, int value) {
        LinkedNode node = cache.get(key);
        if (node == null) {
            if (cache.size() >= capacity) {
                //删除最老的(队首)
                int k = head.key;
                if (tail == head) {
                    head = null;
                    tail = null;
                } else {
                    head.next.pre = null;
                    head = head.next;
                }
                cache.remove(k);
            }
            addNode(key, value);
        } else {
            node.val = value;
            //移动到队尾
            remove2Tail(node);
        }
    }

    private void addNode(int key, int val) {
        LinkedNode newNode = new LinkedNode(key, val);
        cache.put(key, newNode);
        //添加到队尾
        if (head == null && tail == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.pre = tail;
        tail = newNode;
    }

    private void remove2Tail(LinkedNode node) {
        if (node == tail) {
            return;
        }
        //移动到队尾
        if (node == head) {
            node.next.pre = null;
            head = node.next;
        } else {
            LinkedNode pre = node.pre;
            pre.next = node.next;
            node.next.pre = pre;
        }
        tail.next = node;
        node.pre = tail;
        node.next = null;
        tail = node;
    }

    class LinkedNode<k, v> {
        int key;
        int val;

        LinkedNode<k, v> next;
        LinkedNode<k, v> pre;

        LinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
//复杂度O(n)

//    Map<Integer,Integer> cacheMap;
//    Map<Integer,Long> usrKeys;
//    public LRUCache(int capacity) {
//        this.capacity = capacity;
//        cacheMap = new HashMap<>(capacity);
//        usrKeys = new HashMap<>(capacity);
//    }
//
//    public int get(int key) {
//        Integer iii = cacheMap.get(key);
//        if (iii != null) {
//            if (usrKeys.get(key) != null) {
//                //最新时间覆盖
//                usrKeys.put(key, System.nanoTime());
//            } else if (usrKeys.size() == capacity) {
//                //满了 删掉最小的
//                Long min = 9999999999999l;//13位毫秒
//                Integer minKey = null;
//                for (Map.Entry<Integer, Long> e : usrKeys.entrySet()) {
//                    boolean thisMin;
//                    thisMin = e.getValue() < min ? true : false;
//                    if (thisMin) {
//                        min = e.getValue();
//                        minKey = e.getKey();
//                    }
//                }
//                usrKeys.remove(minKey);
//                usrKeys.put(key, System.nanoTime());
//            } else {
//                usrKeys.put(key, System.nanoTime());
//            }
//            return iii;
//        }
//        return -1;
//    }
//
//    public void put(int key, int value) {
//        if (cacheMap.size() == capacity) {
//            if (cacheMap.get(key) != null) {
//                cacheMap.put(key, value);
//            } else {
//                //不存在时淘汰最久未使用的
//
//                Long min = 9999999999999999l;//13位毫秒
//                Integer minKey = null;
//                for (Map.Entry<Integer, Long> e : usrKeys.entrySet()) {
//                    boolean thisMin;
//                    thisMin = e.getValue() < min ? true : false;
//                    if (thisMin) {
//                        min = e.getValue();
//                        minKey = e.getKey();
//                    }
//                }
//                cacheMap.remove(minKey);
//                cacheMap.put(key, value);
//                if (usrKeys.size() == capacity) {
//                    usrKeys.remove(minKey);
//                }
//            }
//        } else {
//            cacheMap.put(key,value);
//        }
//        usrKeys.put(key,System.nanoTime());
//    }

    //["LRUCache","put","put","get","put","get","put","get","get","get"]
    //[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
    //[null,null,null,1,null,-1,null,-1,3,4]
    public static void main1(String[] args) {
//        System.out.println(System.nanoTime());
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        System.out.println("put(1,1)");
        print(cache);
        cache.put(2, 2);
        System.out.println("put(2,2)");
        print(cache);
        cache.get(1);       // 返回  1
        System.out.println("get(1)");
        print(cache);
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        System.out.println("put(3,3)");
        print(cache);
        cache.get(2);
        ;       // 返回 -1 (未找到)
        System.out.println("get(2)");
        print(cache);
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        System.out.println("put(4,4)");
        print(cache);
        System.out.println(cache.get(1));
        ;       // 返回 -1 (未找到)
        System.out.println(cache.get(3));
        ;       // 返回  3
        System.out.println(cache.get(4));
        ;       // 返回  4
    }

    public static void main(String[] args) {
        //["LRUCache","put","put","put","put","get","get"]
        //[[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]

        //["LRUCache","put","put","get","put","get","put","get","get","get"]
        //[[2],[1,0],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

        LRUCache cache = new LRUCache(2);

        cache.put(1, 0);
        cache.put(2, 2);
        print(cache);
        System.out.println("get(1):" );
        System.out.println( cache.get(1));

        System.out.println("put(3,3)");
        cache.put(3, 3);
        System.out.println("get(2):");
        System.out.println(cache.get(2));
        System.out.println("put(4,4)");
        cache.put(4,4);
        print(cache);
        System.out.println("get(1):");
        System.out.println( cache.get(1));
        System.out.println("get(3):" );
        System.out.println(cache.get(3));
        System.out.println("get(4):" );
        System.out.println(cache.get(4));

    }

    private static void print(LRUCache cache) {
        cache.cache.forEach((k, v) -> {
            System.out.println(k + ":" + v.val);
        });

    }
}
